/**
 * 归并排序
 */

/**
 * 归并两个数组
 */
void merge(const int *a, int size_a, const int *b, int size_b, int *c)
{

    int i = 0, j = 0, k = 0;
    while (i < size_a && j < size_b)
    {
        if (b[j] < a[i])
        {
            c[k] = b[j];
            ++j;
        }
        else
        {
            c[k] = a[i];
            ++i;
        }
        ++k;
    }
    /// 另一个不为空，将剩余的元素填入
    // 只有一个for会执行
    for (; j < size_a; ++i, ++k)
    {
        c[k] = a[i];
    }
    for (; j < size_b; ++j, ++k)
    {
        c[k] = b[j];
    }

    return;
}
/**
 * 归并排序（非递归方式）
 */
#include <stdlib.h>
void mergeSort_no_rec(int *a, int n)
{
    int *temp; // 辅助数组，大小最好和a的大小相同
    temp = (int *)malloc(sizeof(int) * n);
    for (int seg = 1; seg < n; seg <<= 1)//seg每次加倍就是左移1位
    {
        for (int left1 = 0; left1 < n - seg; left1 += seg + seg)
        {
            int right1 = left1 + seg; // n-seg：如果最后只有一个段，就不用合并了
            int left2 = right1;
            int right2 = min(left2 + seg, n); // 注意最后一个段的边界
            merge(a + left1, a + right1, a + left2, a + right2, temp + left1);
            for (int i = left1; i < right2; ++i)
                a[i] = temp[i];
        }
    }
}

/**
 * 归并排序（递归实现）
 */
void mergeSort_rec(int *a, int l, int r)
{
    if (r - l <= 1)
        return;
    // 从中间裂开
    int mid = l + ((r - l) >> 1);
    mergeSort_rec(a, l, mid);
    mergeSort_rec(a, mid, r);
    // 合并
    int *tmp; // 临时数组,长度要大于a的长度
    tmp = (int *)malloc(sizeof(int) * 16);
    merge(a + l, a + mid, a + mid, a + r, tmp + l);
}
